package alo.p19;

/**
 * @ClassName Fibonacci
 * @Description 斐波那契数列
 * @Author Fanxc
 * @DATE 2021/3/14 16:12
 * @Version 1.0
 */
public class Fibonacci {
    int fib(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
    int[] fib=new int[100];
    int fib2(int n){
        if (n==0||n==1){
            return 1;
        }
        fib[0]=1;
        fib[1]=1;
        for (int i = 2; i < n; i++) {
            fib[i]=fib[i-1]+fib[i-2];
        }
        return fib[n-1];
    }
    int fib3(int n){
        if (n==1){
            return 1;
        }
        if (n==2){
            return 1;
        }
        if (fib[n]!=0){
            return fib[n];
        }
        return fib[n]=fib3(n-1)+fib3(n-2);
    }
    int fib4(int n){
        int a=0,b=1,sum=0;
        for (int i = 0; i <n; i++) {
            sum=a+b;
            a=b;
            b=sum;
        }
        return sum;
    }
}
